package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-12 19:18
 * @description: Functions of this class is
 * 题意：
 * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
 *
 * 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
 *
 * 说明: ”请不要使用除法“，且在 O(n) 时间复杂度内完成此题。
 *
 * 官方解题：
 * 用动态递归先将当前元素左边及其右边的乘积先算好来，然后直接迭代输出即可，声明R[],L[]两个数组来分别存当前元素左边及其右边的元素的乘积
 * 空间复杂度o(1)解法：
 * class Solution {
 *     public int[] productExceptSelf(int[] nums) {
 *         int length = nums.length;
 *         int[] answer = new int[length];
 *
 *         // answer[i] 表示索引 i 左侧所有元素的乘积
 *         // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
 *         answer[0] = 1;
 *         for (int i = 1; i < length; i++) {
 *             answer[i] = nums[i - 1] * answer[i - 1];
 *         }
 *
 *         // R 为右侧所有元素的乘积
 *         // 刚开始右边没有元素，所以 R = 1
 *         int R = 1;
 *         for (int i = length - 1; i >= 0; i--) {
 *             // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
 *             answer[i] = answer[i] * R;
 *             // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
 *             R *= nums[i];
 *         }
 *         return answer;
 *     }
 * }
 *1：初始化 answer 数组，对于给定索引 i，answer[i] 代表的是 i 左侧所有数字的乘积。
 *2：构造方式与之前相同，只是我们试图节省空间，先把 answer 作为方法一的 L 数组。
 *3：这种方法的唯一变化就是我们没有构造 R 数组。而是用一个遍历来跟踪右边元素的乘积。并更新数组 answer[i]=answer[i]*Ranswer[i]=answer[i]∗R。然后 RR 更新为 R=R*nums[i]R=R∗nums[i]，其中变量 RR 表示的就是索引右侧数字的乘积。
 **/
public class No除自身以外数组的乘积and动态规划解法联动接雨水 {
    public static void main(String args[]){
        int nums[]={1,2,3,4};
        System.out.println(Arrays.toString(productExceptSelf(nums)));
    }
    public static int[] productExceptSelf(int[] nums) {
        int output[]=new int[nums.length];
        int L[]=new int[nums.length];

        L[0]=1;//第一个元素的左边没有元素了，即其乘积位1
        for(int i=1;i<nums.length;i++){
            L[i]=L[i-1]*nums[i-1];//从左往右迭代而去
        }
        output[nums.length-1]=1;//把output数组作为存取其右边元素乘积的数组
        for(int i=nums.length-2;i>=0;i--){
            output[i]=output[i+1]*nums[i+1];

        }
        for(int i=0;i<nums.length;i++){
            output[i]*=L[i];
        }
        return output;
    }

}